package com.xsherl.leetcode.solution;

public class CountTriplets {

    /**
     * a 和 b 定义如下：
     *       a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
     *       b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k - 1]
     *   设 xor[i] = arr[0] ^ ... ^ arr[i - 1]
     *   如果 a == b, 则 xor[i] = xor[k], 此时 j 无论出于什么位置都不影响结果
     *   又因为 j > i , 所以此时有 k - i 种情况
     */
    public int countTriplets(int[] arr) {
        int c = 0;
        int[] xor = new int[arr.length + 1];
        for (int i = 0; i < arr.length; ++i){
            xor[i + 1] = arr[i] ^ xor[i];
        }
        for (int i = 0; i < xor.length - 1; ++i) {
            for (int k = i + 1; k < xor.length; ++k){
                if (xor[i] == xor[k]){
                    c += k - i - 1;
                }
            }
        }
        return c;
    }
}
